package 堆;

import java.util.Arrays;

public class BigHeap {

    public int[] elem;
    public int size;

    public BigHeap() {
        this.elem =new int[10];
    }

    public void creatBigHeap(int[] arr) {
        //给 BigHeap这个对象中的数组进行赋值
        for (int i = 0; i < arr.length; i++) {
            this.elem[i]=arr[i];
            this.size++;
        }

        //parent 代表最后一棵子树 根节点的下标
        for (int parent=(arr.length-1-1)/2;parent>=0;parent--) {
            adjustDown(parent,this.size);
        }

    }

    //向下调整
    private void adjustDown(int root,int length) {
        int parent=root;//根节点下标
        int child=parent*2+1;//根节点的左孩子

        while(child<length) {
            //左孩子的下标 小于 元素总个数 时，可以进行调整

            //判断左右孩子谁的值更大
            if (child+1<length && this.elem[child]<this.elem[child+1]) {
                //如果右孩子的值大，则child++
                child++;
            }

            //此时的child一定是 左右孩子中值更大的下标
            //判断左右孩子能否和根节点互换
            if (this.elem[parent]<this.elem[child]) {
                int tmp=this.elem[parent];
                this.elem[parent]=this.elem[child];
                this.elem[child]=tmp;

                parent=child;//检查当前左右孩子的孩子
                child=parent*2+1;
            }else {
                //调整中，当孩子节点的值没有父亲节点值大，说明当前这棵树已经是大堆了,结束当前这棵树的调整
                break;
            }
        }
    }

    //入队列——向上调整
    public void adjustUp(int child) {
        int parent=(child-1)/2;

        while (parent>0) {
            if (this.elem[child]>this.elem[parent]) {
                //父亲孩子值进行互换
                int tmp=this.elem[parent];
                this.elem[parent]=this.elem[child];
                this.elem[child]=tmp;

                //父亲孩子向上走，继续做判断
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

    //新数值进入队列数组
    public void push(int val) {
        if (isFull()) {
            //扩容
            this.elem=Arrays.copyOf(this.elem,this.elem.length*2);
        }

        this.elem[this.size]=val;
        this.size++;
        adjustUp(this.size-1);

    }
    public boolean isFull() {
        return this.size==this.elem.length;
    }

    //出队列
    public void pop() {
        if (isEmpty()){
            return;
        }

        int tmp=this.elem[0];
        this.elem[0]=this.elem[this.size-1];
        this.elem[this.size-1]=tmp;

        //重新进行一次向下调整
        this.size--;//减少一个元素

        adjustDown(0,this.size);
    }
    public boolean isEmpty() {
        return this.size==0;
    }

    //返回队首元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return this.elem[0];
    }

    //实现 从小到大排序——建立大堆
    public void heapSrot() {
        int end=this.size-1;
        while (end>0) {
            int tmp=this.elem[0];
            this.elem[0]=this.elem[end];
            this.elem[end]=tmp;

            adjustDown(0,end);
            end--;
        }

    }


}
